package mydsl;

import java.util.Arrays;
import java.util.Random;

/**
 * 
 * 各种排序的原理、实现、分析以及对应的资料
 * 
 * 2010-05-18 完成归并排序非递归实现(Bottom-up merge-sort)
 * 
 * @author Haha
 */

public class Sort {
	/**
	 * Insertion Sort - 插入排序
	 * <p>
	 * 
	 * 1. 时间复杂度 O(n^2) (1). 近似有序的序列更容易 (2). 短序列比长序列更容易 (3). 最坏情况：序列反着有序
	 * <p>
	 * 2. 适用场景 (1). 小数据量 (2). 在{@link java.util.Arrays#INSERTIONSORT_THRESHOLD}中，门限被设为7
	 */
	public static void insertionSort(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int key = a[i];
			int j = i - 1;
			while (j >= 0 && a[j] > key) {
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = key;
		}
	}

	/**
	 * Merge Sort - 归并排序
	 * <p>
	 * 
	 * 归并排序实现方式有两种: 递归，非递归 
	 * 使用数据结构有两种: Array-Based，List-Based 
	 * 其中 
	 * (1). 递归，Recursive Array-Based merge-sort，可参考{@link java.util.Arrays#sort(Object[])}
	 * (2). 非递归，Bottom-up merge-sort，可参考书"Data Structures and algorithms in java,4th edition"
	 * 
	 * 改进说明： 
	 * (1). 基于数组的实现使用辅助数组 Use an auxiliary array. 
	 * (2). 数组复制可以使用System.arraycopy()或clone()提高性能 
	 * (3). 合并时，首先判断[是否第一部分的最大值<=第二部分的最小值]，如果是，则直接进行数组复制
	 * (4). 对于小数组引入插入排序，就像{@link java.util.Arrays#sort(Object[])}中所作的那样(Insertion sort on smallest arrays)
	 * 
	 * 1. 时间复杂度 O(NlgN) 
	 * 2. 适用场景 
	 * (1). 在实际中在 n>30 的时候，表现要比插入排序好 
	 * (2). 在实际中非递归实现比基于链表的递归快，虽然时间复杂度一致，但由于避免了额外的递归调用和节点创建。(引自上面书中)
	 */
	public static void mergeSortRecursive(int[] a) {
		int[] aux = new int[a.length];
		System.arraycopy(a, 0, aux, 0, a.length);
		// int[] aux = (int[]) a.clone(); // 可以使用clone方法
		mergeSort(a, aux, 0, a.length);
	}
	
	// 递归实现
	private static void mergeSort(int[] a, int[] aux, int low, int high) {
		// 递归退出条件
		if (low + 1 >= high)
			return;
		int mid = low + (high - low) / 2;
		// 【注意】：技巧所在，这里a, aux进行了交换
		mergeSort(aux, a, low, mid);
		mergeSort(aux, a, mid, high);
		// 合并
		merge(a, aux, low, mid, high);
	}

	// 合并操作
	private static void merge(int[] a, int[] aux, int low, int mid, int high) {
		// i 计数器 p 左标 q 右标
		for (int i = low, p = low, q = mid; i < high; i++) {
			if (q >= high || p < mid && (aux[p] <= aux[q]))
				a[i] = aux[p++];
			else
				a[i] = aux[q++];
		}
	}

	// 非递归实现
	public static void mergeSortNONRecursive(int[] a) {
		int[] aux = new int[a.length];
		System.arraycopy(a, 0, aux, 0, a.length);
		int n = a.length;
		int[] temp;
		for (int i = 1; i < n; i *= 2) {
			for (int j = 0; j < n; j += 2 * i) {
				merge(a, aux, j, Math.min(i + j, n), Math.min(i + i + j, n));
			}
			// 交换a与aux
			temp = a;
			a = aux;
			aux = temp;
		}
	}
	
	/**
	 * QuickSort 插入排序
	 * 
	 * 时间复杂度：O(NlgN)
	 * 
	 * 1. 比归并排序需要更多比较操作，39% more comparisons than mergesort.
	 * 2. 但比归并排序要快(两倍于归并排序)，but faster than mergesort in practice because of lower cost of other high-frequency operations.
	 * 
	 * 说明：
	 * 以下情况可能会导致时间复杂度趋向二次方(quadratic) 
	 * 1. 如果有序(正序或倒序)
	 * 2. 有很多重复(Has many duplicates)[可以调优]
	 */
	public static void quickSort(int[] a) {
		quickSort(a, 0, a.length - 1);
	}
	
	private static void quickSort(int[] a, int low, int high) {
		if(low < high) {
			int q = partition(a, low, high);
			quickSort(a, low, q-1);
			quickSort(a, q+1, high);
		}
	}

	private static int partition(int[] a, int low, int high) {
		int x = a[low];
		int i = low;
		for(int j=low+1; j<=high; j++) {
			if(a[j] <= x) {
				i = i+1;
				swap(a, i, j);
			}
		}
		swap(a, low, i);
		return i;
	}

	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public static void main(String[] args) {
		// 随机构造20个元素的数组
		int n = 20;
		Random r = new Random();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = r.nextInt(100);
		}
		System.out.println("排序前: " + Arrays.toString(a));
		Sort.quickSort(a);
		System.out.println("排序后: " + Arrays.toString(a));
	}

}
